#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0020.py
@time: 2021/9/16 12:54
@desc: https://leetcode-cn.com/problems/word-search-ii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hui-s-am8f/
'''


class Solution:
    def __init__(self):
        self.words_set = set()  # 记录单词的集合
        self.ans = []  # 答案
        self.dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]  # 方向

    def findWords(self, _board: list, words: list) -> list:
        # 回溯法框架：https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3%E4%BF%AE%E8%AE%A2%E7%89%88.md

        def dfs(i, j, sb):
            # 结束条件
            if len(sb) > 10: return  # 字符串过长
            # 找到满足条件的
            if sb in self.words_set:
                self.ans.append(sb)
                # 删除掉已经找到的
                self.words_set.remove(sb)

            # 未找到就向其他方向前进寻找
            for d in self.dirs:
                # 下一个方向的坐标
                dx, dy = i + d[0], j + d[1]
                # 越界则退出
                if dx < 0 or dx >= m or dy < 0 or dy >= n: continue
                # 访问过则退出
                if vis[dx][dy]: continue
                vis[dx][dy] = True
                # 做选择
                sb += board[dx][dy]
                # dfs
                dfs(dx, dy, sb)
                # 回溯（删除选择）
                vis[dx][dy] = False
                sb = sb[:-1]

        board = _board
        m, n = len(board), len(board[0])
        vis = [[False for j in range(n)] for i in range(m)]
        for w in words: self.words_set.add(w)

        # 路径，即track
        sb = ''
        i, j = 0, 0
        while i < m:
            j = 0
            while j < n:
                # 做选择
                vis[i][j] = True
                sb += board[i][j]
                # 回溯
                dfs(i, j, sb)
                # 取消选择
                vis[i][j] = False
                sb = sb[:-1]
                j += 1
            i += 1

        return self.ans

if __name__ == '__main__':
    sl = Solution()
    board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
    words = ["oath","pea","eat","rain"]
    ans = sl.findWords(board, words)
    print(ans)